/**
* Created with CLion.
* User:Lenovo
* Date:2023-05-26
* Time:22:24
* Description:洛谷 P4779  单源最短路径
*/

/* 堆(优先队列)优化的 dijkstra 算法 */

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>

#define maxM 200050
#define maxN 100050

typedef struct Edge
{
    int to;
    int next;
    int w;
} Edge;

typedef struct Heap
{
    Edge *edge;// edge 数组
    int size;
    int capacity;
} Heap;

Edge edgeG[maxM];
int head[maxN], dist[maxN];
bool visited[maxN];
int count = 0;// edge 里有多少数据

void add(int u, int v, int w)
{
    edgeG[count].to = v;
    edgeG[count].w = w;
    edgeG[count].next = head[u];
    head[u] = count++;
}

void Init()
{
    for (int i = 0; i < maxN; i++)
    {
        head[i] = -1;
        dist[i] = INT_MAX;
        visited[i] = false;
    }
}

void HeapInit(Heap *pHp)
{
    pHp -> edge = NULL;
    pHp -> size = 0;
    pHp -> capacity = 0;
}

void Swap(Edge *a, Edge *b)
{
    Edge tmp = *a;
    *a = *b;
    *b = tmp;
}

void AdjustUp(Edge *edge, int child)
{
    int parent = (child - 1) / 2;

    while (child > 0)
    {
        if (edge[child].w < edge[parent].w)
        {
            Swap(edge + child, edge + parent);
            child = parent;
            parent = (parent - 1) / 2;
        }
        else
        {
            break;
        }
    }
}

void AdjustDown(Edge *edge, int n, int parent)
{
    int child = parent * 2 + 1;

    while (child < n)
    {
        if (child + 1 < n && edge[child].w > edge[child + 1].w)
        {
            child += 1;
        }

        if (edge[parent].w > edge[child].w)
        {
            Swap(edge + parent, edge + child);
            parent = child;
            child = child * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

void Push(Heap *pHp, Edge x)
{
    if (pHp -> size == pHp -> capacity)
    {
        int newCapacity = (pHp -> edge == NULL ? 4 : 2 * pHp -> capacity);
        Edge *newEdge = (Edge *)realloc(pHp -> edge, sizeof(Edge) * newCapacity);
        if (newEdge == NULL)
        {
            perror("realloc error");
            return;
        }
        pHp -> edge = newEdge;
        pHp -> capacity = newCapacity;
    }

    pHp -> edge[pHp -> size++] = x;
    AdjustUp(pHp -> edge, pHp -> size - 1);
}

bool HeapEmpty(Heap *pHp)
{
    return pHp -> size == 0;
}

void Pop(Heap *pHp)
{
    Swap(pHp -> edge, pHp -> edge + pHp -> size - 1);
    pHp -> size--;
    AdjustDown(pHp -> edge, pHp -> size, 0);
}

Edge Top(Heap *pHp)
{
    return pHp -> edge[0];
}

void dijkstra(int x, Heap *hp)
{
    Edge tmp = {0, -1, 0};
    Push(hp, tmp);

    while (!HeapEmpty(hp))
    {
        if (!HeapEmpty(hp))
        {
            tmp = Top(hp);// 取队顶值
            Pop(hp);// 出队

            if (visited[tmp.to]) // 如果已经确定了最短路径，说明有重边，直接跳过即可
            {
                continue;
            }

            x = tmp.to;
            visited[x] = true;// 表示已经确定了最短路径的点
        }

        for (int i = head[x]; i != -1; i = edgeG[i].next)
        {
            int y = edgeG[i].to;
            if (dist[y] > edgeG[i].w + dist[x]) // s 点到 edge[i].to 的距离 w 小于原距离
            {
                dist[y] = edgeG[i].w + dist[x];// 更新 dist
                if (!visited[y]) // 如果已经确定最短路径，就不要再次入队指向 y 的边了，因为一定不是最短的
                {
                    edgeG[i].w = dist[y];/* 注意更新边权值：这里放的应该是原点到 y 的距离而不是边权 */
                    Push(hp, edgeG[i]);// 入队
                }
            }
        }
    }
}

int main()
{
    Init();
    Heap hp;
    HeapInit(&hp);

    int n, m, s;
    scanf("%d %d %d", &n, &m, &s);
    int u, v, w;
    for (int i = 0; i < m; i++)
    {
        scanf("%d %d %d", &u, &v, &w);
        add(u - 1, v - 1, w);
    }

    s -= 1;
    dist[s] = 0;

    dijkstra(s, &hp);

    for (int i = 0; i < n; i++)
    {
        printf("%d ", dist[i]);
    }

    return 0;
}